import itertools

# 数据集示例
data = [
    ['Milk', 'Bread', 'Butter'],
    ['Milk', 'Bread'],
    ['Milk', 'Butter'],
    ['Bread', 'Butter'],
    ['Milk', 'Bread', 'Butter', 'Cheese'],
    ['Bread', 'Butter', 'Cheese']
]


def create_initial_candidates(data):
    """
    创建初始候选项集（单个商品）
    """
    items = set()
    for transaction in data:
        items.update(transaction)
    return sorted(items)


def generate_candidate_k_itemsets(frequent_itemsets, k):
    """
    根据上一轮的频繁项集生成新的候选项集
    """
    candidates = []
    for i in range(len(frequent_itemsets)):
        for j in range(i + 1, len(frequent_itemsets)):
            l1 = list(frequent_itemsets[i])
            l2 = list(frequent_itemsets[j])
            l1.sort()
            l2.sort()
            if l1[:k - 2] == l2[:k - 2]:
                candidates.append(tuple(set(l1) | set(l2)))
    return candidates


def compute_support(data, candidates):
    """
    计算候选项集的支持度
    """
    support_data = {}
    total_transactions = len(data)
    candidate_counts = {c: 0 for c in candidates}

    # 计算每个候选项集在数据集中出现的次数
    for transaction in data:
        for candidate in candidates:
            if set(candidate).issubset(transaction):
                candidate_counts[candidate] += 1

    # 转换为支持度比例
    for candidate, count in candidate_counts.items():
        support_data[candidate] = count / total_transactions

    return support_data


def apriori(data, min_support):
    """
    实现Apriori算法
    """
    C1 = create_initial_candidates(data)
    D = [set(transaction) for transaction in data]
    frequent_itemsets = []
    L1 = prune_by_min_support(D, C1, min_support)
    frequent_itemsets.append(L1)
    k = 2
    while (len(frequent_itemsets[k - 2]) > 0):
        Ck = generate_candidate_k_itemsets(frequent_itemsets[k - 2], k)
        Lk = prune_by_min_support(D, Ck, min_support)
        frequent_itemsets.append(Lk)
        k += 1
    return frequent_itemsets


def prune_by_min_support(data, candidates, min_support):
    """
    根据最小支持度阈值进行剪枝，返回频繁项集
    """
    support_data = compute_support(data, candidates)
    return {item: sup for item, sup in support_data.items() if sup >= min_support}


# 设置最小支持度
min_support = 0.5

# 调用Apriori算法并输出结果
frequent_itemsets = apriori(data, min_support)

for k, itemsets in enumerate(frequent_itemsets, start=1):
    print(f"频繁{k}-项集:")
    for itemset, support in itemsets.items():
        print(f"  {itemset}: 支持度 = {support:.2f}")